\section{Allocating 2 Facilities to 3 Agents: The Proof of Theorem~\ref{thm:3agents}}
\label{s:3agents}

%We start with the proof of Theorem~\ref{thm:3agents}, for which we need some additional notation.
%\noindent{\bf Notation.}
%
Throughout this section, we use the indices $i, j, k$ to implicitly define a permutation of the agents. We mostly use the convention that $i$ denotes the leftmost agent, $j$ denotes the middle agent, and $k$ denotes the rightmost agent. %If a few different instances are involved, this convention applies to the first instance.

We recall that given a nice mechanism $F$ with approximation ratio $\rho$ for $3$ agents, a $3$-agent instance $\vec{x}$ is \emph{$(i | j, k)$-well-separated} if $x_i < x_j < x_k$ and $\rho(x_k - x_j) < x_j - x_i$. Similarly, $\vec{x}$ is \emph{$(i, j | k)$-well-separated} if $x_i < x_j < x_k$ and $\rho(x_j - x_i) < x_k - x_j$.
%
A $3$-agent instance $\vec{x}$ is \emph{$i$-left-well-separated} if $\vec{x}$ is either $(i|j,k)$-well-separated or $(i|k,j)$-well-separated, and is \emph{$k$-right-well-separated} if it is either $(i,j|k)$-well-separated or $(j,i|k)$-well-separated. Moreover, a $3$-agent instance $\vec{x}$ is \emph{$i$-well-separated} if $\vec{x}$ is either $i$-left-well-separated or $i$-right-well-separated.

In the following, we let $\uparrow$ and $\downarrow$ denote the largest and the smallest element, respectively, of the affinely extended real line. Hence, $\uparrow$ is greater than any real number, and $\downarrow$ is less than any real number.


\subsection{Outline of the Proof}
\label{s:outline}

%We proceed to establish Theorem~\ref{thm:3agents}, which is the crux, and the most technically involved part, of the proof of Theorem~\ref{thm:2fac-gen}.

%\noindent{\bf Outline.}
%
At a very high-level, the proof of Theorem~\ref{thm:3agents} proceeds by gradually restricting the possible outcomes of a nice mechanism, until it reaches the desired conclusion. %The proof essentially proceeds in three main steps, each establishing the desired conclusion for a different level of generality.

As a first step, we consider the behavior of a nice mechanism for well-separated instances (Section~\ref{s:well-separated}). Since the mechanism has a bounded approximation ratio, for any $i$-well-separated instance, one facility serves the isolated agent $i$, and the other facility is placed between the locations of the two nearby agents $j$, $k$. Thus, building on the characterization of \cite{Moul80}, we show that for any $i$-well-separated instance, the facility serving $j$ and $k$ is allocated by a generalized median voter scheme (GMVS) (see e.g. \cite[Definition~10.3]{SV07}) whose characteristic threshold may depend on the identity $i$ and the location $a$ of the isolated agent (Lemma~\ref{l:single-p} and Lemma~\ref{l:i-separated}). A bit more formally, we show, in Lemma~\ref{l:i-separated}, that any agent-location pair $(i, a)$ specifies a unique threshold $p \in [a, +\infty) \union \{ \uparrow \}$ and a preferred agent $j$, different from $i$, that fully determine the location of the rightmost facility for all $i$-left-well-separated instances $\vec{x}$ with $x_i = a$ (see also Fig.~\ref{fig:allocation}.a; by symmetry, the same holds for $i$-right-well-separated instances and the leftmost facility, though possibly with different values of $p$ and $j$). Moreover, the allocation of the rightmost facility becomes simple for the two extreme values of the $p$: if $p = a$, the preferred agent $j$ serves as a dictator imposed by $i$ for all $i$-left-well-separated instances, while if $p =\,\uparrow$, the rightmost facility is placed at the rightmost location.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\insertfig{0.95\textwidth}{figures/plot}{\label{fig:allocation}%
(a) The location of $F_2(\vec{x})$ for all $i$-left-well-separated instances $\vec{x}$ with $x_i = a$. We let $j$ be the preferred agent and $p$ be the threshold of $(i, a)$ for $i$-left-well-separated instances. The location of agent $j$ (resp. $k$) is on the $x$-axis (resp. $y$-axis). The area around the line $x_j = x_k$ includes all $i$-left-well-separated instances. For instances in the grey area (where $x_j \leq x_k \leq p$), the rightmost facility is at $x_k$, for instances in the black triangle (where $x_j \leq p \leq x_k$), the rightmost facility is at $p$, and for instances in the light grey area (where either $x_j \geq p$ or $x_k \leq x_j \leq p$), the rightmost facility is at $x_j$. %We highlight that the smaller the value of $p$, the larger the area where $F_2(\vec{x}) = x_j$.
%
(b) We consider instances $\vec{x}$ with $x_i = a < x_j, x_k$, which are not necessarily well-separated. As in (a), we let $j$ be the preferred agent and $p$ be the threshold of $(i, a)$. 
%The location of agent $j$ (resp. $k$) is on the $x$-axis (resp. $y$-axis). 
The plot now depicts for which instances a facility (not necessarily the rightmost one) is placed at either $x_j$, or $x_k$, or $p$.
%
%By Lemma~\ref{l:non-separated}, for all instances $\vec{x}$ with $x_j \geq p$ (the light grey area on the right), $x_j \in F(\vec{x})$. By Lemma~\ref{l:non-separated-inside}, for all instances $\vec{x}$ with $a < x_j, x_k \leq p$, $F_2(\vec{x}) = \max\{x_j, x_k\}$. Therefore, for instances in the (dark grey) upper-left part of the square $a < x_j, x_k \leq p$, the rightmost facility is allocated to $x_k$, while for instances in the (light grey) lower-right part, the rightmost facility is allocated to $x_j$. Finally, by Lemma~\ref{l:approx}, for all instances $\vec{x}$ with $a < x_j < x_k$ and $x_k$ large enough (the light grey area on the top-left corner), $x_j \in F(\vec{x})$.
%
Lemma~\ref{l:i-cases} essentially shows that due to the bounded approximation ratio of $F$, the black triangle does not exist, and either $p = a$ or $p =\,\uparrow$. If $p = a$, we have light grey (i.e., $x_j$) everywhere, while if $p = \,\uparrow$, we have dark grey (i.e., $x_k$) above the line $x_j = x_k$, and light grey (i.e., $x_j$) below.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


The key step in the proof of Theorem~\ref{thm:3agents} is to show, in Section~\ref{s:gen-instances}, that the threshold $p$ of any agent-location pair $(i, a)$ can be either $a$ or $\uparrow$ (resp. either $a$ or $\downarrow$ if $i$ is the rightmost agent).
%
To this end, we first extend the allocation rule of Lemma~\ref{l:i-separated} to instances that have $i$ as their leftmost (resp. rightmost) agent and are not necessarily well-separated (see Fig.~\ref{fig:allocation}.b).
%
%In a nutshell, we show that for most such instances, the threshold $p$ and the preferred agent $j$, that determine the location of a facility on the right (resp. left) part of the instance, %may depend on the identity $i$ and the location $a$ of the leftmost (resp. rightmost) agent, and
%are the same as those for $i$-left (resp. $i$-right) well-separated instances.
Thus, if the preferred agent $j$ is located on the right (resp. left) of the threshold $p$, she essentially serves as a partial dictator, imposed by the leftmost (resp. rightmost) agent, for the corresponding permutation of agents.

As consequence, we obtain that the thresholds of the two allocation rules (one imposed by the leftmost agent and one imposed by the rightmost agent) always fall in the two extremes: either $a$ or $\uparrow$ for the leftmost agent (resp. either $a$ or $\downarrow$ for the rightmost agent). Otherwise, there would exist instances with two different preferred agents, essentially serving as two different partial dictators, which would lead to an unbounded approximation ratio (Lemma~\ref{l:i-cases}). Intuitively, the case where $p = a$ corresponds to the existence of a partial dictator, while the case where $p =\,\uparrow$ (resp. $p =\,\downarrow$) corresponds to placing the facilities at the two extremes.

%Building on Lemma~\ref{l:i-cases}, we show, in Section~\ref{s:3agent-fin}, that every nice mechanism is essentially characterized by whether there are two agents that agree on imposing the third agent as a partial dictator or not. By examining all possible cases, we conclude that every nice mechanism $F$ either always places the facilities at the two extremes, or admits a partial dictator $j$ (Lemma~\ref{l:3agents}).

Building on Lemma~\ref{l:i-cases}, we show, in Section~\ref{s:3agent-fin}, that the thresholds of the two allocation rules, one for the leftmost and one for the rightmost agent, can only depend on their identity, and not on their location (Lemma~\ref{l:always-a}). Moreover, if an agent $i$ imposes a partial dictator, the third agent agrees with $i$ not only on the existence of a partial dictator, but also on the dictator's identity (Lemma~\ref{l:others-a}), and the partial dictator is unique (Lemma~\ref{l:only-dictator}).
%
Therefore, every nice mechanism is essentially characterized by whether there are two agents that agree on imposing the third agent as a partial dictator or not. By examining all possible cases, we conclude that every nice mechanism $F$ either always places the facilities at the two extremes, or admits a partial dictator $j$ (Lemma~\ref{l:3agents}).
%
In the latter case, the partial dictator $j$ is identified by any instance $\vec{x}$, with $x_i < x_j < x_k$, such that $x_j \in F(\vec{x})$. %Then, $F$ allocates a facility to agent $j$ for all instances $\vec{y}$ with $y_i < y_j < y_k$, and possibly for all instances $\vec{y}$ with $y_k < y_j < y_i$. For all other instances, $F$ places the facilities at two extremes.



\subsection{Well-Separated Instances}
\label{s:well-separated}

%We start by considering the behavior of a nice mechanism on well-separated instances.
For simplicity and brevity, we mostly discuss left-well-separated instances, for which we state and prove all our technical claims. It is straightforward to verify that the symmetric statements of all our lemmas %, propositions, and technical arguments
hold for right-well-separated instances.

For any $(i | j, k)$-well-separated instance $\vec{x}$, the leftmost facility $F_1(\vec{x})$ of a nice mechanism $F$ serves the isolated agent $i$, and the rightmost facility $F_2(\vec{x})$ is allocated in $[x_j, x_k]$.
%
Intuitively, with both the order of $j$ and $k$ and the range of $F_2(\vec{x})$ fixed, the restriction of $F$ to the $2$-agent subinstance $\vec{x}_{-i}$ should behave like an anonymous strategyproof mechanism that places a single facility in $[x_j, x_k]$. Therefore, the rightmost facility should be allocated by a median voter scheme applied to $x_j$ and $x_k$ (see e.g. \cite[Theorem~10.2]{SV07}). The following lemma, whose proof can be found in the Appendix, Section~\ref{app:s:single-p}, formalizes this intuition:

 %it shows that $F_2(\vec{x}) = \med(p, x_j, x_k)$, where $p$ may depend on the identity $i$ and the location $a$ of the isolated agent, and also on the relative order of the nearby agents $j$ and $k$.

\begin{lemma}\label{l:single-p}
For any agent $i \in \{1, 2, 3\}$ and any location $a$, there exists a unique threshold $p \in [a, +\infty) \union \{ \uparrow \}$ such that for all $(i | j, k)$-well-separated instances $\vec{x}$ with $x_i = a$, it holds that $F_2(\vec{x}) = \med(p, x_j, x_k)$.
\end{lemma}

At the conceptual level, the allocation of $F_2(\vec{x})$ to $i$-left-well-separated instances $\vec{x}$ corresponds to a GMVS applied to the subinstance $\vec{x}_{-i}$.
%
We recall that a GMVS applied to a set $N$ of agents is characterized by $2^{|N|}$ thresholds $\alpha_S$, one for each $S \subseteq N$ (see e.g. \cite[Definition~10.3]{SV07}), with $\alpha_\emptyset$ (resp. $\alpha_N$) equal to the smallest (resp. largest) value in the mechanism's range. Then, for every instance $\vec{x}$, the facility is allocated to $\max_{S \subseteq N}\min\{ \alpha_S, x_i \!:\! i \in S\}$.
%
Lemma~\ref{l:single-p} implies that there is a unique threshold $p_1$ (resp. $p_2$) such that for any $(i | j, k)$-well-separated (resp. $(i |k, j)$-well-separated) instance $\vec{x}$ with $x_i = a$, $F_2(\vec{x}) = \med(p_1, x_j, x_k)$ (resp. $F_2(\vec{x}) = \med(p_2, x_j, x_k)$).
%
Therefore, for any $i$-left-well-separated instance $\vec{x}$ with $x_i = a$, a GMVS applied to the subinstance $\vec{x}_{-i}$ is characterized by $\alpha_{\{j\}} = p_2$ and $\alpha_{\{k\}} = p_1$. Setting $\alpha_\emptyset = a$ and $\alpha_{\{j, k\}} =\,\uparrow$, it holds that
%
$F_2(\vec{x}) = \max\{ \min\{ x_j, p_2 \}, \min\{ x_k, p_1 \} \}$.

The following lemma, whose detailed proof can be found in the Appendix, Section~\ref{app:s:i-separated}, shows that due to the bounded approximation ratio of $F$, either $p_1 =\,\uparrow$ or $p_2 =\,\uparrow$. If $p_2 =\,\uparrow$, $j$ has at least as much power as $k$, and becomes the preferred agent of the agent-location pair $(i, a)$ for $i$-left-well-separated instances. Then, the threshold $p$ of $(i, a)$ is equal to $p_1$, and $F_2(\vec{x}) = \max\{ x_j, \min\{ x_k, p \} \}$ (see also Fig.~\ref{fig:allocation}.a). We note that %the smaller the value of $p$, the greater the power of the preferred agent $j$. Thus,
the threshold $p$ essentially quantifies how much more powerful is the preferred agent $j$ than the third agent $k$. At the two extremes, if $p = a$, $j$ serves as a dictator on the right of $i$, while if $p =\,\uparrow$, the rightmost facility is allocated to the maximum of $x_j$ and $x_k$.
%
Similarly, if $p_1 =\,\uparrow$, $k$ is the preferred agent of the agent-location pair $(i, a)$ for $i$-left-well-separated instances, and $p = p_2$. Then, $F_2(\vec{x}) = \max\{ \min\{ x_j, p \}, x_k, \}$.

%Next, we show that for all $i$-left-well-separated instances, the rightmost facility is determined by a GMVS, whose characteristic ``thresholds'' may depend on the identity $i$ and the location $a$ of the isolated agent, but not on the relative order of $j$ and $k$.
%

\begin{lemma}\label{l:i-separated}
For any agent $i \in \{1, 2, 3\}$ and any location $a$, there exist a unique threshold $p \in [a, +\infty) \union \{ \uparrow \}$ and a preferred agent $\ell \in \{1, 2, 3\} \setminus \{ i \}$ such that for any $i$-left-well-separated instance $\vec{x}$ with $x_i = a$, it holds that $F_2(\vec{x}) = x_\ell$, if $x_\ell \geq p$, and $F_2(\vec{x}) = \med(p, x_j, x_k)$, otherwise.
%
%\[ F_2(\vec{x}) = \left\{
%    \begin{array}{ll}
%        x_\ell   & \mbox{if $x_\ell \geq p$}\\[1pt]
%        \med(p, x_j, x_k)\ \ \ &\mbox{otherwise}
%    \end{array}\right.\]
\end{lemma}

By a symmetric argument, we can establish the symmetric version of Lemma~\ref{l:i-separated} for $i$-right-well-separated instances. The only difference is that $p \in \{ \downarrow \} \union (-\infty, a]$, and that $F_1(\vec{x}) = x_\ell$, if $x_\ell \leq p$, and $F_1(\vec{x}) = \med(p, x_j, x_k)$, otherwise. %We highlight that an agent location pair $(i, a)$ may have a different preferred agent and a different threshold for $i$-left and $i$-right well-separated instances.

Lemma~\ref{l:i-separated} implies that every nice mechanism $F$ admits a function $\l_F$ (resp. $\r_F$) % : \{ 1, 2, 3\} \times \reals \mapsto \{ 1, 2, 3 \} \times (\reals \union \{ \uparrow \})$
that maps any agent-location pair $(i, a)$ to a pair $(j, p)$, where $p \in [a, +\infty) \union \{ \uparrow \}$ (resp. $p \in \{ \downarrow \} \union (-\infty, a]$) is the unique threshold and $j \in \{1, 2, 3\} \setminus \{ i \}$ is the preferred agent of $(i, a)$ satisfying the condition of (resp. the symmetric version of) Lemma~\ref{l:i-separated} for $i$-left (resp. $i$-right) well-separated instances.
%
%Similarly, every nice mechanism $F$ admits a function $\r_F : \{ 1, 2, 3\} \times \reals \mapsto \{ 1, 2, 3 \} \times (\reals \union \{ \downarrow \})$ that maps any agent-location pair $(i, a)$ to a pair $(\ell, p)$, where $p \in \{ \downarrow \} \union (-\infty, a]$ is the unique threshold and $\ell \in \{1, 2, 3\} \setminus \{ i \}$ is the preferred agent of $(i, a)$ satisfying the condition of the symmetric version of Lemma~\ref{l:i-separated} for $i$-right-well-separated instances.
%
We note that the preferred agent is uniquely determined in the proof of Lemma~\ref{l:i-separated}, unless $p =\,\uparrow$ for $i$-left (resp. $p =\,\downarrow$ for $i$-right) well-separated instances. If $p = \,\uparrow$ (resp. $p =\,\downarrow$), any agent different from $i$ can play the role of the preferred agent, since this choice does not affect the allocation of $F_2(\vec{x})$ (resp. $F_1(\vec{x})$). For convenience, we simply write $\l(i, a)$ and $\r(i, a)$, %instead of $\l_F(i, a)$ and $\r_F(i, a)$,
%whenever the mechanism $F$ is clear from the context. Moreover, we
and let $\l_p(i, a)$ and $\l_\ell(i, a)$ (resp. $\r_p(i, a)$ and $\r_\ell(i, a)$) denote the threshold $p$ and the preferred agent $j$ of $(i, a)$ for $i$-left (resp. $i$-right) well-separated instances.
%
Lemma~\ref{l:i-separated} implies the following:

%Before we proceed to the second step of the proof, we state the following corollary of Lemma~\ref{l:i-separated}.

\begin{corollary}\label{cor:dict-location}
Let $\vec{x}$ be any $(i|j,k)$-well-separated instance. If $F_2(\vec{x}) = x_j$, then $\l_\ell(i, x_i) = j$ and $\l_p(i, x_i) \leq x_j$.
\end{corollary}

%A detailed proof of Corollary~\ref{cor:dict-location} can be found in the Appendix, Section~\ref{app:s:dict-location}. By a symmetric argument, we obtain the symmetric version of the corollary: for any $(i,j|k)$-well-separated instance $\vec{x}$, the leftmost facility cannot be allocated to the middle agent $j$, unless $\r_\ell(i, x_i) = j$ and $\r_p(i, x_i) \geq x_j$.



\subsection{General Instances and the Range of the Threshold $p$}
\label{s:gen-instances}

We proceed to show that $\l_p(i, a) \in \{a, \uparrow\}$ (and by symmetry, $\r_p(i, a) \in \{a, \downarrow\}$). As before, we consider the instances from left to right, and state and prove our lemmas in terms of $\l(i, a)$. It is straightforward to verify that the symmetric statements hold for $\r(i, a)$.

We start with three useful technical lemmas that essentially extend the allocation of Lemma~\ref{l:i-separated} to instances that are not necessarily well-separated (see also Fig.~\ref{fig:allocation}.b).
%
%Using these lemmas, we determine where the location of the facility serving (at least one of) the agents $j$ and $k$ for most of the undecided areas in Fig.~\ref{fig:allocation}.a, and obtain Fig.~\ref{fig:allocation}.b.
%
The first lemma shows that the preferred agent essentially serves as a dictator when located on the right of the threshold $p$.
%
%The proofs of Lemma~\ref{l:non-separated-inside} and Lemma~\ref{l:approx} are similar to the proof of Lemma~\ref{l:non-separated} and can be found in the Appendix, Section~\ref{app:s:non-separated-inside}, and Section~\ref{app:s:approx}, respectively.


%
%Their proofs are similar and can be found in the Appendix, Sections~\ref{app:s:non-separated}, \ref{app:s:non-separated-inside}, and \ref{app:s:approx}, respectively. In all of them, the proof idea is to assume an instance that violates the lemma, and taking advantage of the corresponding hole in the image set, to construct a well-separated instance for which $F$ has an unbounded approximation ratio.


\begin{lemma}\label{l:non-separated}
Let $i$ be any agent and $a$ be any location, and let $\l(i, a) = (j, p)$. For any instance $\vec{x}$ with $a = x_i < \min\{x_j, x_k\}$, and $x_j \geq p$, it holds that $x_j \in F(\vec{x})$.
\end{lemma}

\begin{proof}
%Let us fix an agent $i$ and some location $a$. By Lemma~\ref{l:i-separated}, there are a threshold $p \in [a, +\infty) \union \{ \uparrow \}$ and a preferred agent $j \in \{1, 2, 3\} \setminus \{ i \}$ such that for any $i$-left-well-separated instance $\vec{y}$ with $y_i = a$ and $y_j \geq p$, $y_j \in F_2(\vec{y})$. We next show that for the particular $p$ and $j$, and for any instance $\vec{x}$ with $x_i = a$ and $x_j \geq p$, $x_j \in F(\vec{x})$.
%
We fix an agent $i$ and some location $a$, and let $\l(i, a) = (j, p)$. For sake of contradiction, we assume that there is an instance $\vec{x}$, with $x_i = a$ and $x_j \geq p$, such that $x_j \not\in F(\vec{x})$. Therefore, $x_j$ does not belong to the image set $I_j(x_i, x_k)$, and there is a $x_j$-hole $(l, r)$ in $I_j(x_i, x_k)$. For a small $\eps \in (0, \min\{(r-l)/2, r-x_j\})$, we consider the instance $\vec{x}' = (\vec{x}_{-j}, r-\eps)$. Since $r-\eps$ is in the right half of the $x_j$-hole $(l, r)$, $r \in F(\vec{x}')$. Now, we consider the instance $\vec{x}'' = (\vec{x}_{-\{j,k\}}, r-\eps, r)$, and show that $F(\vec{x}'') = (r-\eps, r)$. On the one hand, $r \in F(\vec{x}'')$, because $F$ is strategyproof. On the other hand, we can choose $\eps$ small enough that the instance $\vec{x}''$ is $(i|j,k)$-well-separated. Then, by Lemma~\ref{l:i-separated}, $x''_j \in F(\vec{x}'')$, because by the choice of $\eps$, $x''_j = r-\eps > x_j \geq p$. However, this implies that $x_i$ is served by the facility at $r-\eps$, which contradicts $F$'s bounded approximation ratio.
\qed\end{proof}


%By a symmetric argument, we obtain the symmetric version of Lemma~\ref{l:non-separated} for instances where $i$ is the rightmost agent: if $\r(i, a) = (j, p)$, for all instances $\vec{x}$ with $x_i = a$, $x_i > \max\{ x_j, x_k \}$, and $x_j \leq p$, $x_j \in F(\vec{x})$.
%
The next lemma shows that if both agents $j$ and $k$ are located (on the right of agent $i$ and) on the left of $p$, the rightmost facility is allocated to the rightmost agent. The proof is similar to the proof of Lemma~\ref{l:non-separated}, and can be found in the Appendix, Section~\ref{app:s:non-separated-inside}.


\begin{lemma}\label{l:non-separated-inside}
Let $i$ be any agent and $a$ be any location, and let $\l_p(i, a) = p$. For any instance $\vec{x}$ with $x_i = a$ and $x_j, x_k \in (x_i, p]$, it holds that $F_2(\vec{x}) = \max\{x_j, x_k\}$.
\end{lemma}

%By a symmetric argument, we obtain the symmetric version of Lemma~\ref{l:non-separated-inside} for instances where $i$ is the rightmost agent: if $\r_p(i, a) = p$, for all instances $\vec{x}$ with $x_i = a > x_j, x_k \geq p$, $F_1(\vec{x}) = \min\{x_j, x_k\}$.

%The proof of Lemma~\ref{l:non-separated-inside} is similar to the proof of Lemma~\ref{l:non-separated}, and can be found in the Appendix, Section~\ref{app:s:non-separated-inside}.
%
The next lemma complements the previous two, and shows that the preferred agent is allocated a facility even if she lies on the left of $p$ and is not the rightmost agent, provided that the distance of the rightmost agent to $p$ is large enough.

\begin{lemma}\label{l:approx}
Let $\rho$ be the approximation ratio of $F$, let $i$ be any agent and $a$ be any location, and let $\l(i, a) = (j, p)$. Then, for any instance $\vec{x}$ with $a = x_i < x_j < x_k$, and $x_k - p > \rho(p - x_i)$, it holds that $x_j \in F(\vec{x})$.
\end{lemma}

\begin{proof}
We fix an agent $i$ and some location $a$, and let $\l(i, a) = (j, p)$.
%
%By Lemma~\ref{l:non-separated}, there are a $p \in [a, +\infty) \union \{ \uparrow \}$ and an agent $j \in \{1, 2, 3\} \setminus \{ i \}$ such that for any instance $\vec{y}$ with $y_i = a$ and $y_j \geq p$, $y_j \in F_2(\vec{y})$. We next show that for the particular $p$ and $j$, and for any instance $\vec{x}$ with $x_i = a$, $x_i < x_j < x_k$ and $x_k - p > \rho(p - x_i)$, $x_j \in F(\vec{x})$.
%
For sake of contradiction, let us assume that there is an instance $\vec{x}$ with $a = x_i < x_j < x_k$ and $x_k - p > \rho(p - x_i)$, for which $x_j \not\in F(\vec{x})$. Therefore, $x_j$ does not belong to the image set $I_j(x_i, x_k)$, and there is a $x_j$-hole $(l, r)$ in $I_j(x_i, x_k)$. Moreover, $x_j < p$ and $r \leq p$, because by Lemma~\ref{l:non-separated}, for any $y \geq p$, $y \in F(\vec{x}_{-j}, y)$. Since $F$ is strategyproof, for any point $x'_j$ in the right half of the hole $(l, r)$, $r \in F(\vec{x}_{-j}, x'_j)$. By Proposition~\ref{prop:middle}, $F_1(\vec{x}_{-j}, x'_j) \leq x'_j$, and thus $r = F_2(\vec{x}_{-j}, x'_j)$. Therefore, $x_k$ is served by the facility at $r$, and $\cost[F(\vec{x}_{-j}, x'_j)] \geq x_k - p$. This contradicts the hypothesis that the approximation ratio is $\rho$, since the optimal cost for $(\vec{x}_{-j}, x'_j)$ is at most $x'_j - x_i \leq p - x_i < (x_k - p) / \rho$.
\qed\end{proof}

Now, we are ready to show that the threshold $p$ always falls in the two extremes.%, thus making a major step towards the proof of Theorem~\ref{thm:3agents}.

\begin{lemma}\label{l:i-cases}
For any agent $i$ and location $a$, $\l_p(i, a) \in \{a, \uparrow \}$ and $\r_p(i, a) \in \{a, \downarrow \}$.
\end{lemma}

\begin{proof}
We show that $\l_p(i, a) \in \{a, \uparrow \}$. The claim that $\r_p(i, a) \in \{a, \downarrow \}$ follows by a symmetric argument.
%
For sake of contradiction, let us assume that there exist an agent $i$ and a location $a$, for which $p_i \equiv \l_p(i, a) \in (a, +\infty)$, and let $j = \l_\ell(i, a)$.
%
To reach a contradiction, we study the preferred agents of four appropriately chosen well-separated instances $\vec{x}$, $\vec{y}$, $\vec{z}$, and $\vec{w}$. Intuitively, exploiting the properties of the instances $\vec{x}$, $\vec{y}$, $\vec{z}$, we show that in the last instance $\vec{w}$, where the agents are arranged according to the permutation $(i, j, k)$, the preferred agent of $(i, w_i)$ on the right is $j$ and the preferred agent of $(k, w_k)$ on the left is $i$. Moreover, $\vec{w}$ is chosen to satisfy the conditions of Lemma~\ref{l:approx} for $i$ and her preferred agent $j$ (see also Fig.~\ref{fig:instances}). This implies a facility allocation for $\vec{w}$ with an approximation ratio larger than $F$'s approximation ratio $\rho$, a contradiction.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\insertfig{0.8\textwidth}{figures/instances}{\label{fig:instances}%
The four instances considered in the proof of Lemma~\ref{l:i-cases} with the corresponding thresholds and preferred agents. A square indicates that a facility is placed at the corresponding location. A star indicates that the corresponding agent is the preferred agent of the agent-location pair appearing next to the star.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Formally, let the first instance $\vec{x}$ be any $(i|j,k)$-well-separated instance such that $x_j < p_i < x_k$ and the instance $(\vec{x}_{-i}, p_i)$ is $(j|i,k)$-well-separated. Then, by Lemma~\ref{l:i-separated}, $F_2(\vec{x}) = \med(p_i, x_j, x_k) = p_i$.
%
The second instance is $\vec{y} = (\vec{x}_{-i}, p_i)$, which is $(j|i,k)$-well-separated, by the choice of $\vec{x}$. Moreover, $F_2(\vec{y}) = p_i = y_i$, due to $F$'s strategyproofness. We let $p_j \equiv \l_p(j, y_j)$. Then, by Corollary~\ref{cor:dict-location}, $\l_\ell(j, y_j) = i$ and $p_j \leq y_i$.

The third instance is $\vec{z} = (\vec{y}_{-k}, r)$, where $r$ is chosen so that $r - p_i > \rho(p_i - a)$, where $\rho$ is the approximation ratio of $F$. Therefore, $\vec{z}$ is a $(j, i |k)$-well-separated instance. Since $y_j = z_j$, $\l(j, z_j) = (i, p_j)$ and $p_j \leq z_i$. Hence, we apply Lemma~\ref{l:non-separated} to the instance $\vec{z}$, and obtain that $z_i \in F(\vec{z})$. Therefore, by (the symmetric of) Corollary~\ref{cor:dict-location} applied to the $(j, i |k)$-well-separated instance $\vec{z}$, $\r_\ell(k, r) = i$ and $\r_p(k, r) \equiv p_k \geq z_i$.

The fourth instance is $\vec{w} = (\vec{x}_{-k}, r)$. Since $w_i = a$, we have that $\l(i, w_i) = (j, p_i)$. Since the location $r$ of $k$ in $\vec{w}$ is chosen so that $r - p_i > \rho(p_i - w_i)$, we apply Lemma~\ref{l:approx} to $\vec{w}$, and obtain that $w_j \in F(\vec{w})$. Moreover, by the choice of $r$, $\vec{w}$ is an $(i, j|k)$-well-separated instance. Therefore, since $\r_\ell(k, r) = i$ and $\r_p(k, r) \geq z_i \geq w_i$, by (the symmetric of) Lemma~\ref{l:i-separated} applied to the $k$-right-well-separated instance $\vec{w}$, $F_1(\vec{w}) = w_i$. By the choice of $r$, the hypothesis that $F$'s approximation ratio is $\rho$, since $\cost[F(\vec{w})] = r - w_j > r - p_i$, while the optimal cost for $\vec{w}$ is $w_j - w_i < p_i - a < (r - p_i) / \rho$.
\qed\end{proof}




\subsection{On the Existence of a Partial Dictator}
\label{s:3agent-fin}

%In this section, we conclude the proof of Theorem~\ref{thm:3agents}.
%
Having restricted the range of $p$ to the two extremes, we can make some useful observations about the preferred agents and the thresholds of the leftmost and the rightmost locations. We start with the following consequence of Lemma~\ref{l:i-cases} and Corollary~\ref{cor:dict-location}.

\begin{proposition}\label{prop:dict-location-a}
If there is an $(i|j,k)$-well-separated instance $\vec{x}$, such that $F_2(\vec{x}) = x_j$, then $\l(i, x_i) = (j, x_i)$. If there is an $(i,j|k)$-well-separated instance $\vec{x}$, such that $F_1(\vec{x}) = x_j$, then $\r(k, x_k) = (j, x_k)$.
\end{proposition}

The following lemma shows that the preferred agent and the threshold of an agent $i$ can only depend on her identity, and not on her location.

\begin{lemma}\label{l:always-a}
Let $i$ be an agent and $a$ be a location such that $\l(i, a) = (j, a)$ (resp. $\r(i, a) = (j, a)$). Then, for all locations $b \in \reals$, $\l(i, b) = (j, b)$ (resp. $\r(i, b) = (j, b)$).
\end{lemma}

\begin{proof}
We only show that if $\l(i, a) = (j, a)$, then $\l(i, b) = (j, b)$, for all locations $b$. The other case follows from a symmetric argument.
%
Let $i$ be an agent and $a$ be a location such that $\l(i, a) = (j, a)$, for some agent $j$, and let $b$ be any location. To show that $\l(i, b) = (j, b)$, we consider two appropriate instances $\vec{x}$ and $\vec{y}$.

The instance $\vec{x}$ is defined as $x_i = a$, $x_j = a + 1$, and $x_k = r > \max\{a+1, b\}$, where $r$ is chosen large enough that $\vec{x}$ is an $(i,j|k)$-well-separated instance. Since $x_j \geq \l_p(i, a)$,  Lemma~\ref{l:non-separated} implies that $x_j \in F(\vec{x})$. Then, since $\vec{x}$ is an $(i,j|k)$-well-separated instance, by Proposition~\ref{prop:dict-location-a}, $\r(k, r) = (j, r)$.

The instance $\vec{y}$ is defined as $y_i = b$, $y_j = r-\eps$, and $y_k = r$, where $\eps > 0$ is chosen so small that $\vec{y}$ is an $(i|j,k)$-well-separated instance. Since $y_j \leq \r_p(k, r)$, the symmetric version of Lemma~\ref{l:non-separated} applied to $\vec{y}$ implies that $y_j \in F(\vec{y})$. Then, since the instance $\vec{y}$ is $(i|j,k)$-well-separated, by Proposition~\ref{prop:dict-location-a},
$\l(i, b) = (j, b)$.
 \qed\end{proof}

Next, Lemma~\ref{l:others-a} shows that if an agent $i$ imposes another agent $j$ as a partial dictator, the third agent $k$ agrees with $i$ not only on the existence of a partial dictator, but also on the partial dictator's identity.
%
Moreover, Lemma~\ref{l:only-dictator} shows that if there is an agent $j$ imposed as a partial dictator by the leftmost and the rightmost agent, then $j$ is the only agent with this property. Thus, if $j$ is located at the one extreme of the instance, the other facility is placed at the other extreme.
%
The proofs of the following lemmas can be found in the Appendix, Section~\ref{app:s:others-a} and Section~\ref{app:s:only-dictator}, respectively.


\begin{lemma}\label{l:others-a}
If there exists an agent $i$ and a location $a$ such that $\l(i, a) = (j, a)$ (resp. $\r(i, a) = (j, a)$), then for the third agent $k$ and all locations $b \in \reals$, it holds that $\r(k, b) = (j, b)$ (resp. $\l(k, b) = (j, b)$).
\end{lemma}

\begin{lemma}\label{l:only-dictator}
If there exists an agent $i$ and a location $a$ such that $\l(i, a) = (j, a)$, then for all locations $b \in \reals$, it holds that $\l_p(j, b) =\,\uparrow$ and $\r(j, b) =\,\downarrow$.
\end{lemma}


Now, we are are ready to conclude the proof of Theorem~\ref{thm:3agents}. We show that the behavior of any nice mechanism $F$ is essentially characterized by whether there are two agents that agree on imposing the third agent as a partial dictator or not. Theorem~\ref{thm:3agents} is an immediate consequence of the following lemma.

\begin{lemma}\label{l:3agents}
Either for all instances $\vec{y}$, $F(\vec{y}) \in ( \min \vec{y}, \max \vec{y} )$, or there exists an instance $\vec{x}$, with $x_i < x_j < x_k$, such that $x_j \in F(\vec{x})$. In the latter case:
%
\begin{itemize}
\item For all instances $\vec{y}$ with $y_i < y_j < y_k$, $y_j \in F(\vec{y})$.

\item Either for all instances $\vec{y}$ with $y_k < y_j < y_i$, $y_j \in F(\vec{y})$, or for all instances $\vec{y}$ with $y_k < y_j < y_i$,
    $F(\vec{y}) = ( \min \vec{y}, \max \vec{y} )$

\item For all the remaining instances $\vec{y}$, $F(\vec{y}) = ( \min \vec{y}, \max \vec{y} )$
\end{itemize}
\end{lemma}


\begin{proof}
We distinguish between the case where for all agents $i \in \{ 1, 2, 3\}$ and for all locations $a \in \reals$, $\l_p(i, a) =\,\uparrow$, and the case where there exists an agent $i \in \{ 1, 2, 3\}$ and a location $a \in \reals$ such that $\l_p(i, a) = a$. Lemma~\ref{l:i-cases} implies that these two cases are indeed complementary to each other.

\smallskip\noindent{\bf Case I: $\forall i \forall a \, \l_p(i, a) =\,\uparrow$.}
%
We show that in this case, $F$ always places the facilities at two extremes.
%
To this end, we let $\vec{x}$ be any instance, and let $i$ be the leftmost agent and $k$ be the rightmost agent in $\vec{x}$. By hypothesis, $\l_p(i, x_i) =\,\uparrow$. Therefore, by Lemma~\ref{l:non-separated-inside}, $F_2(\vec{x}) = x_k$.
%
Moreover, $\r_p(k, x_k) =\,\downarrow$, since otherwise, it would be $\r_p(k, x_k) = x_k$, by Lemma~\ref{l:i-cases}, and thus $\l_p(i, x_i) = x_i$, by Lemma~\ref{l:others-a}, which contradicts the hypothesis. Therefore, by the symmetric version of Lemma~\ref{l:non-separated-inside}, $F_1(\vec{x}) = x_i$.


\smallskip\noindent{\bf Case II: $\exists i \exists a \, \l_p(i, a) = a$.}
%
We let $(i, a)$ be any agent-location pair with $\l_p(i, a) = a$, let $j = \l_\ell(i, a)$ be the preferred agent of $i$, and let $k$ be the third agent. Therefore, for all locations $b$, $\l_p(j, b) =\,\uparrow$ and $\r_p(j, b) =\,\downarrow$, by Lemma~\ref{l:only-dictator}. We next show that in this case, the agent $j$ serves as a partial dictator, and satisfies the latter case of the conclusion.

We first observe that for all locations $a' \in \reals$, $\l(i, a') = (j, a')$, by Lemma~\ref{l:always-a}, and $\r(k, a') = (j, a')$, by Lemma~\ref{l:others-a}. Therefore, for all instances $\vec{x}$ with $x_i < x_k$, $x_j \in F(\vec{x})$. More specifically, if $x_i < x_j$, this follows from Lemma~\ref{l:non-separated}, while if $x_j < x_k$, this follows from the symmetric version of Lemma~\ref{l:non-separated}. Then, using Lemma~\ref{l:non-separated-inside}, we obtain the conclusion of the lemma for all instances $\vec{x}$ with $x_i < x_k$\,:

\begin{itemize}
\item For all instances $\vec{x}$ with $x_i < x_j < x_k$, $x_j \in F(\vec{x})$.

\item For all instances $\vec{x}$ with $x_j < x_i < x_k$, $F_1(\vec{x}) = x_j$ and $F_2(\vec{x}) = x_k$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(j, x_j) =\,\uparrow$. Therefore, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$.

\item For all instances $\vec{x}$ with $x_i < x_k < x_j$, $F_2(\vec{x}) = x_j$ and $F_1(\vec{x}) = x_i$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(j, x_j) =\,\downarrow$. Therefore, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$.
\end{itemize}

As for instances $\vec{x}$ with $x_k < x_i$, we first show that either $\l(k, b) = (j, b)$ or $\l_p(k, b) =\,\uparrow$, for all locations $b$ (i.e., we exclude the possibility that for some $b$, $\l(k, b) = (i, b)$). In the former case, the facilities are allocated similarly to the case where $x_i < x_k$. In the latter case, the facilities are placed at the two extremes. The details can be found in the Appendix, Section~\ref{app:s:3agents-lemma}.
\qed\end{proof}

\endinput



\subsection{On the Existence of a Partial Dictator}
\label{s:3agent-fin}

%In this section, we conclude the proof of Theorem~\ref{thm:3agents}.
%
Having restricted the range of $p$ to the two extremes, we are now ready to conclude the proof of Theorem~\ref{thm:3agents}. %We show that the behavior of any nice mechanism $F$ is essentially characterized by whether there are two agents that agree on imposing the third agent as a partial dictator or not.
Theorem~\ref{thm:3agents} is an immediate consequence of the following:


\begin{lemma}\label{l:3agents}
Either for all instances $\vec{y}$, $F(\vec{y}) \in ( \min \vec{y}, \max \vec{y} )$, or there exists an instance $\vec{x}$, with $x_i < x_j < x_k$, such that $x_j \in F(\vec{x})$. In the latter case:
%
\begin{itemize}
\item For all instances $\vec{y}$ with $y_i < y_j < y_k$, $y_j \in F(\vec{y})$.

\item Either for all instances $\vec{y}$ with $y_k < y_j < y_i$, $y_j \in F(\vec{y})$, or for all instances $\vec{y}$ with $y_k < y_j < y_i$,
    $F(\vec{y}) = ( \min \vec{y}, \max \vec{y} )$

\item For all the remaining instances $\vec{y}$, $F(\vec{y}) = ( \min \vec{y}, \max \vec{y} )$
\end{itemize}
\end{lemma}

\begin{proofsketch}
Building on Lemma~\ref{l:i-cases}, we first show that the thresholds of the two allocation rules can only depend on the identity of the leftmost and the rightmost agent, and not on their location. Moreover, if an agent $i$ imposes a partial dictator, the third agent agrees with $i$ not only on the existence of a partial dictator, but also on the dictator's identity, and the partial dictator is unique.
%
Therefore, every nice mechanism is essentially characterized by whether there are two agents that agree on imposing the third agent as a partial dictator or not.

To conclude the proof, we distinguish between the case where for all agents $i \in \{ 1, 2, 3\}$ and for all locations $a \in \reals$, $\l_p(i, a) =\,\uparrow$, and the case where there exists an agent $i$ and a location $a$ such that $\l_p(i, a) = a$. In the former case, we show that $F$ always places the facilities at two extremes, while in the latter case, we show that the preferred agent of $(i, a)$ serves as a partial dictator, and the allocation of $F$ satisfies the latter case of the conclusion.
%
The details can be found in Appendix~\ref{app:s:l:3agents}.
\qed\end{proofsketch}



\endinput



